using System;
using System.Collections.Generic;

namespace GridRegulator
{
    public static class LineLocator
    {
        /* for peak / ditch */
        const int kW = 32;

        /* for pulseq */
        const int kGap = 16;
        const int kMaxDragLen = 16;

        /* for periodian */
        const double kThr11 = 0.1;
        const double kThr12 = 0.03;
        const double kThr2 = 0.05;
        const double kCredPFract = 0.1;

        /* for sync */
        const int kTries = 2;
        const int kMargin = 8;


        static bool[] Peak(double[] levels)
        {
            bool[] peaks = new bool[levels.Length];
            int i = 0;

            foreach (double level in levels)
            {
                int lefti = Math.Max(i - kW, 0);
                int righti = Math.Min(i + kW + 1, levels.Length);
                bool ispeak = true;

                for (int j = lefti; j < righti; j++)
                {
                    if (levels[j] > level)
                    {
                        ispeak = false;
                        break;
                    }
                }

                peaks[i] = level > 0 && ispeak;
                i++;
            }

            return peaks;
        }

        static bool[] Ditch(double[] levels)
        {
            double[] ditches = new double[levels.Length];
            
            for (int i = 0; i < levels.Length; i++)
            {
                double level = levels[i];
                double mean = 0;
                int lefti = Math.Max(i - kW, 0);
                int righti = Math.Min(i + kW + 1, levels.Length);

                for (int j = lefti; j < righti; j++)
                {
                    mean += levels[j];
                }
                mean /= righti-lefti;

                bool nt = false;
                double hi = mean;

                bool leftn = false;
                bool rightn = false;

                for (int j = i - 1; j >= lefti; j--)
                {
                    if (levels[j] > hi)
                    {
                        hi = levels[j];
                        nt = true;
                    }
                    else if (nt)
                    {
                        double nd = (hi + level) / 2;
                        if (levels[j] < nd)
                        {
                            leftn = true;
                            break;
                        }
                    }
                }

                hi = mean;
                nt = false;
                for (int j = i + 1; j < righti; j++)
                {
                    if (levels[j] > hi)
                    {
                        hi = levels[j];
                        nt = true;
                    }
                    else if (nt)
                    {
                        double nd = (hi + level) / 2;
                        if (levels[j] < nd)
                        {
                            rightn = true;
                            break;
                        }
                    }
                }

                bool skip = leftn && rightn;
                if (mean > level && !skip)
                {
                    ditches[i] = (mean - level) / mean;
                }
                else
                {
                    ditches[i] = 0;
                }
            }

            bool[] peaks = Peak(ditches);
            for (int i = 0; i < kW; i++)
            {
                peaks[i] = false;
                peaks[peaks.Length - i - 1] = false;
            }
                return peaks;
        }

        static List<int> Pulseq(bool[] input)
        {
            List<int> output = new List<int>();

            int nstrips = 0;
            int ilaststrip = -kGap;
            int draglen = 0;

            for (int i = 0; i < input.Length; i++)
            {
                if (input[i] == false)
                {
                    continue;
                }
                int d = i - ilaststrip;
                if (d < kGap)
                {
                    draglen += d;
                    if (draglen > kMaxDragLen)
                    {
                        if (nstrips > 0)
                        {
                            output.RemoveAt(output.Count - 1);
                        }
                        nstrips = 0;
                    }
                    else
                    {
                        output[output.Count - 1] += i; 
                        nstrips++;
                    }
                }
                else
                {
                    if (output.Count > 0 && nstrips > 1)
                    {
                        output[output.Count - 1] += nstrips>>1;
                        output[output.Count - 1] /= nstrips;
                    }
                    output.Add(i);
                    draglen = 0;    /* not in dragging state now */
                    nstrips = 1;
                }
                ilaststrip = i;
            }

            if (nstrips > 1)
            {
                output[output.Count - 1] += nstrips >> 1;
                output[output.Count - 1] /= nstrips;
            }

            return output;
        }

        static int AppxMul(double a, double b, double t)
        {
            if (b == 0)
            {
                if (a == 0) return 1;
                return -1;
            }

            double r = a / b;
            double fmul = Math.Round(r);

            r = r - fmul;
            if (!(r > -t && r < t))
            {
                return -1;
            }

            return (int)fmul;
        }

        static bool Periodian(List<int> pulsesIn,
            out List<int> pulsesLeft, out List<int> pulsesRight,
            out List<int> pulsesBase, out int credperiod)
        {
            return Periodian(pulsesIn, kThr12, out pulsesLeft,
                out pulsesRight, out pulsesBase, out credperiod);
        }

        static bool Periodian(List<int> pulsesIn, double thr12,
            out List<int> pulsesLeft, out List<int> pulsesRight,
            out List<int> pulsesBase, out int credperiod)
        {
            pulsesLeft = new List<int>();
            pulsesRight = new List<int>();
            pulsesBase = null;
            int credbase;
            credperiod = 0;

            List<int> pulses = new List<int>();
            double period = 0;
            int noccur = 0;
            List<int> psv_pulses = new List<int>();
            double psv_period = 0;
            int psv_noccur = 0;

            int xlast = -1;

            
            /* find out the most probable period and its representative pulses */

            for (int i = 0; i < pulsesIn.Count; i++)
            {
                int x = pulsesIn[i];
                if (xlast < 0)
                {
                    xlast = x;
                    continue;
                }

                int d = x - xlast;
                if (noccur == 1 && Math.Abs(d-period)<kThr11*period
                    || noccur > 1 && Math.Abs(d-period)<kThr12*period)
                {
                    if (noccur == 1)
                    {
                        period = d;
                        noccur = 2;
                    }
                    else
                    {
                        period *= noccur;
                        period += d;
                        noccur++;
                        period /= noccur;
                    }
                    pulses.Add(x);
                }
                else
                {
                    if (noccur > 0)
                    {
                        if (noccur > psv_noccur)
                        {
                            psv_period = period;
                            psv_noccur = noccur;
                            psv_pulses = pulses;
                        }
                        pulses = new List<int>();
                    }
                    period = d;
                    noccur = 1;
                    pulses.Add(xlast);
                    pulses.Add(x);
                }

                xlast = x;
            }   /* for */

            if (psv_noccur > noccur)
            {
                noccur = psv_noccur;
                pulses = psv_pulses;
                period = psv_period;
            }

            /* get the base */

            if (noccur >= 2)
            {
                credbase = pulses[1];
                int n = (int)Math.Round((pulses[pulses.Count - 1] - pulses[1]) / period);
                credperiod = (pulses[pulses.Count - 1] - pulses[1] + (n>>1)) / n;
            }
            else if (noccur == 1)
            {
                credbase = pulses[0];
                credperiod = pulses[1] - pulses[0];
            }
            else
            {
                return false;
            }

            int pgroupbegin = pulses[0];
            int pgroupend = pulses[pulses.Count - 1];

            /* 
             * based on the period just found, accept more pulses that 
             * occur at its multiples
             */

            for (int i = 0; i < pulsesIn.Count; i++)
            {
                int x = pulsesIn[i];
                if (x < pgroupbegin)
                {
                    if (AppxMul(credbase - x, credperiod, kThr2) > 0)
                    {
                        pulsesLeft.Add(x);
                    }
                }
                else if (x > pgroupend)
                {
                    if (AppxMul(x - credbase, credperiod, kThr2) > 0)
                    {
                        pulsesRight.Add(x);
                    }
                }
                else
                {
                    continue;
                }
            }

            pulsesBase = pulses;

            return true;
        }   /* Periodian */

        public static bool Sync(GrayImage gray, out int vbeginp, out int vendp, 
            out int vn, out int hbeginp, out int hendp, out int hn)
        {
            int dhlow = 0;
            int dhhigh = gray.Height-1;
            int dvlow = 0;
            int dvhigh = gray.Width-1;

            vbeginp = vendp = 0;
            hbeginp = hendp = 0;
            vn = hn = 0;

            int phbegin, phend;
            int pvbegin, pvend;
            int pvp = 0, php = 0;
            List<int> phl = null, phr = null, phb = null;
            List<int> pvl = null, pvr = null, pvb = null;

            for (int itry = 0; itry < kTries; itry++)
            { 
                double[] vh = LineVariation.ComputeHorizontal(gray, dvlow, dvhigh-dvlow+1);
                double[] vv = LineVariation.ComputeVertical(gray, dhlow, dhhigh - dhlow + 1);

                bool[] dh = Ditch(vh);
                bool[] dv = Ditch(vv);

                List<int> seqh = Pulseq(dh);
                List<int> seqv = Pulseq(dv);

                bool bh = Periodian(seqh, out phl, out phr, out phb, out php);
                if (!bh) return false;

                bool bv = Periodian(seqv, out pvl, out pvr, out pvb, out pvp);
                if (!bv) return false;

                phbegin = (phl.Count > 0)? phl[0] : phb[0];
                phend = (phr.Count > 0) ? phr[phr.Count - 1] : phb[phb.Count - 1];
                pvbegin = (pvl.Count > 0)? pvl[0] : pvb[0];
                pvend = (pvr.Count > 0) ? pvr[pvr.Count - 1] : pvb[pvb.Count - 1];

                dhlow = Math.Max(0, phbegin - kMargin);
                dhhigh = Math.Min(gray.Height - 1, phend + kMargin);
                dvlow = Math.Max(0, pvbegin - kMargin);
                dvhigh = Math.Min(gray.Width - 1, pvend + kMargin);
            }

            int phb1 = phb.Count > 2 ? phb[1] : phb[0];
            int pvb1 = pvb.Count > 2 ? pvb[1] : pvb[0];

            phbegin = (phl.Count > 0) ? phl[0] : phb1;
            phend = (phr.Count > 0) ? phr[phr.Count - 1] : phb[phb.Count - 1];
            pvbegin = (pvl.Count > 0) ? pvl[0] : pvb1;
            pvend = (pvr.Count > 0) ? pvr[pvr.Count - 1] : pvb[pvb.Count - 1];

            int nhbegin = (phb1 - phbegin + (php>>1)) / php;
            int nhend = (phend - phb1 + (php >> 1)) / php;
            int nvbegin = (pvb1 - pvbegin + (pvp >> 1)) / pvp;
            int nvend = (pvend - pvb1 + (pvp >> 1)) / pvp;

            hn = nhbegin + nhend;
            vn = nvbegin + nvend;

            hbeginp = phb1 - nhbegin * php;
            hendp = phb1 + nhend * php;
            vbeginp = pvb1 - nvbegin * pvp;
            vendp = pvb1 + nvend * pvp;

            return true;
        }

    }   /* class LineLocator */
}   /* namespace GridRegulator */